#leetcode题目94：二叉树的中序遍历
#难度：简单

#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：递归


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from typing import List
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
       def dfs(root, res):
           if not root:
               return
           dfs(root.left, res)
           res.append(root.val)
           dfs(root.right, res)
       res = []
       dfs(root, res)
       return res

#测试数据

root=[1,None,2,3]
root=TreeNode(1,None,TreeNode(2,TreeNode(3,None,None),None))
#预期输出：[1,3,2]
solution = Solution()
print(solution.inorderTraversal(root))







